Problem statement: zenit13kkh

Maroško sa rozhodol, že spraví reformu regionálneho členenia. Namiesto žúp vytvorí prirodzené regióny. Jednou z vecí, ktorú potrebuje vyriešiť, je vybrať centrá pre nové územnosprávne celky.

Obce v regióne si predstavíme ako body v rovine. Maroško sa vo veľkom necháva inšpirovať Spojenými štátmi americkými. Preto budeme na určenie vzdialenosti dvoch bodov používať takzvanú Manhattanovskú metriku. Vzdialenosť bodov A = [a_x,a_y] a B = [b_x,b_y] je počítaná ako dist(A,B) = |a_x − b_x| + |a_y − b_y| (teda súčet absolútnych hodnôt rozdielov súradníc). Napríklad vzdialenosť bodov [3,5] a [2,9] je |3−2| + |5 − 9| = 5.

Maroško pozná súradnice obcí v regióne a jeho úlohou je jedno zo sídiel označiť ako centrum. V centre budú všetky úrady a preto tam obyvatelia budú musieť často cestovať. Maroško by teda chcel, aby bola súhrnná dĺžka presunu čo najmenšia. Počet obyvateľov nebudeme uvažovať. Pri našich výpočtoch budeme každú obec uvažovať ako rovnocennú.

Pre zvolené centrum môžeme pre každú obec v regióne spočítať vzdialenosť k tomuto centru. Zistite minimálnu hodnotu súčtu týchto vzdialeností pri vhodnej voľbe centra.

Na prvom riadku vstupu je počet obcí N (1 ≤ N ≤ 100,000). Na ďalších N riadkoch sú súradnice jednotlivých obcí. Všetky súradnice sú celé čísla medzi 0 a 1000 vrátane. Žiadne dve obce nebudú na rovnakom mieste. Na výstup vypíšte jediné číslo - hľadanú minimálnu hodnotu.

Za rozumné korektné riešenie s časovou zložitosťou N² môžete očakávať približne polovicu bodov. Vzorové riešenie od N závisí len lineárne. Poznámka: V tejto úlohe je pamäťový limit 128 MB.

4
0 1
2 1
4 2
3 4 

9 

2
0 0
54 31 

85 

6
17 5
0 3
9 11
3 14
10 10
8 17 

49